package com.kevinkk.tree;

/**
 * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵平衡二叉搜索树。
 *
 * 不需要不断的申请、复制新的数组，而是通过双指针的方式进行移动
 */

public class ConvertSortedArrayToBinarySearchTree {
    class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            return build(nums, 0, nums.length-1);
        }

        private TreeNode build(int[] nums, int l, int r){
            if(l > r) return null;
            int mid = (l+r) / 2;
            TreeNode root = new TreeNode(nums[mid]);
            root.left = build(nums, l, mid-1);
            root.right = build(nums, mid+1, r);
            return root;
        }
    }
}
